package code201_300.code40_50;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
 *
 * 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
 *
 * 输入: s = "anagram", t = "nagaram"
 * 输出: true
 *
 * 输入: s = "rat", t = "car"
 * 输出: false
 *
 */
public class _242isAnagram {

    /**
     * 思考：想到了抵消的方法，可以将字符串替换成数字，然后进行异或即可。（我真是个天才）
     * 这样的话 无论是ascii或其他码字符 都可以。空间复杂度n，时间复杂度n
     *
     * 拒绝花里胡哨：
     * 方法1：排序，对每个字符串以字符或数字形式进行排序比较即可，时间最小nlogn，空间最小n
     * 方法2：维护一个hash表，统计频次即可，时间n，空间n
     * 执行用时：     * 15 ms     * , 在所有 Java 提交中击败了     * 19.50%     * 的用户
     * 内存消耗：     * 39 MB     * , 在所有 Java 提交中击败了     * 19.80%     * 的用户
     *
     * 排序：
     * 执行用时：     * 3 ms     * , 在所有 Java 提交中击败了     * 74.26%     * 的用户
     * 内存消耗：     * 38.5 MB     * , 在所有 Java 提交中击败了     * 69.01%     * 的用户
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        //排序
        /*if (s.length() != t.length()) {
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);*/

        if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Integer> table = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            table.put(ch, table.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            table.put(ch, table.getOrDefault(ch, 0) - 1);
            if (table.get(ch) < 0) {
                return false;
            }
        }
        return true;
    }
}
